



%\section{Formulazione del problema e obiettivi}
%Lo scopo di questo progetto è l'ottimizzazione della copertura di un percorso per obiettivi di videosorveglianza, impiegando delle telecamere PTZ come sensori. Le singole telecamere sono degli \emph{agenti}, nel senso che implementano al loro interno un algoritmo di controllo che funziona in modo distribuito. Ciascun agente copre una porzione del percorso e può comunicare almeno con i due agenti adiacenti. Lungo il percorso possono accadere degli \emph{eventi}, che alterano la dinamica normale di monitoraggio. 
%\\L'obiettivo e' quello di massimizzare la copertura del percorso cercando al contempo di fare il  \emph{tracking} degli eventi che possono accadere.
%
%\section{Caso base - Approccio iniziale}
%Prima di affrontare il problema nella sua forma più generale (telecamere aventi coperture e velocità differenti, possibili sovrapposizioni delle aree di sorveglianza, introduzione di evento avente dinamica complessa) abbiamo cercato di affrontarne una versione semplificata, al fine di comprendere a fondo quelle che potevano essere le problematiche da affrontare ed avere una base implementativa da cui partire in seguito. 
%\\Le ipotesi di quello che possiamo definire ``caso base'' sono:
%\begin{enumerate}
%\item Telecamere aventi tutte la stessa velocità massima, $V_{max}$
%\item Zone di copertura costanti ed uguali per ogni telecamera ($C_i = C_j = L$, \\$\forall i,j $)
%\item Zone di copertura disgiunte ($C_i \cap C_j$ = $\emptyset$)
%\end{enumerate}
%
%\paragraph{Struttura dei dati:}
%\begin{itemize}
%\item $C_i$ range di copertura delle telecamera i-esima (tutti lunghi $L$) 
%\item $S_i(t)$ sezione vista dalla telecamera i-esima all'istante $t$ ($S_i \subseteq C_i$)
%\item pos(t) vettore che contiene la posizione di ciascuna telecamera all'istante $t$
%\item pos(0) variabile aleatoria uniformemente distribuita tra 0 e 1000 per ogni telecamera
%\item $V_{max}$ = 10 (a ogni istante mi sposto al più di 10 passi)
%\end{itemize}
%
%\paragraph{Osservazione:}
%Il percorso da monitorare è stato discretizzato: ciascuna $C_i$ ha una certa risoluzione (posta uguale a 1000), la posizione di ciascuna telecamera assume un valore intero compreso tra 1 e 1000 e il range di visione (field of view (fov), lunghezza di $S_i$) è stato posto pari a 100 (10 \% del segmento $C_i$ da esplorare); la velocità massima come scritto sopra vale 10.
%
%\paragraph{Obiettivo:}
%Cercare di coordinare le telecamere nella loro normale azione di patrolling, ottenendo la miglior copertura possibile in assenza di eventi.
%\paragraph{Idea della soluzione proposta}
%Abbiamo pensato di adoperare due funzionali per descrivere la dinamica di ciascuna telecamera: uno che tenga conto del tempo trascorso dall'ultima visita della telecamera stessa, l'altro che permetta di coordinare le telecamere secondo l'ottimo da noi presupposto:
%\begin{enumerate}
%\item $Jpos_i(x,t) =\left\{\begin{array}{l}
%                   {0 \mbox{ , se $x \in S_i$}}\\
%                   {(t-t_{ultimaVisita})^2 \mbox{ , altrimenti}}\\
%                   \end{array}\right.$ 
%\item $Jcoor_i(x,t) = -k(x-pos_{i-1}(t))^2  - k(x-pos_{i+1}(t))^2$
%\end{enumerate}
%con $x$ intero $\in$ [1 \ldots 1000].\\
%Ad ogni istante si calcola $J_i(x,t) = Jpos_i(x,t) + Jcoor_i(x,t)$ e la posizione ottima per la telecamera i-esima all'istante $t+1$ sarà: 
%$$pos_i(t+1) = \arg\max_x\, [J_i(x,t)]$$
%con $k$ parametro su cui tarare l'ampiezza del funzionale di coordinazione.
%\\In questo modo si cerca di minimizzare il massimo assunto dal funzionale $J_i$ ad ogni passo (vedi formalizzazione più rigorosa successivamente), scelta che ci sembrava ragionevole e che porterà a regime le telecamere ad effettuare il patrolling alla velocità massima assegnata.
%\\La nostra idea quindi era quella di coordinare le telecamere per la funzione di patrolling in modo tale che a regime esse fossero tutte a distanza pari a $L$, supponendo che questo potesse essere utile per un'eventuale generalizzazione futura in cui le velocità delle telecamere fossero diverse e si avessero anche zone di copertura sovrapposte (ipotesi 1, 3 rilassate, mentre per come era stato concepito il funzionale di coordinazione il rilassamento dell'ipotesi 2 avrebbe probabilmente creato qualche problema in più). 
%
%\paragraph{Scelta del funzionale di coordinazione}
%Per raggiungere il nostro obiettivo abbiamo creato il funzionale di coordinazione come la somma di due parabole con la concavità rivolta verso il basso il cui centro (e massimo) fosse rispettivamente la posizione della telecamera $i-1$ e $i+1$ (in questo modo lo spostamento ottimo suggerito ad $i$ da entrambe le telecamere adiacenti è di trovarsi a distanza $L$ da loro); la scelta della parabola è legata al fatto che il minimo (o massimo in questo caso) di una parabola è ben definito e la somma di due parabole con vertice sull'asse $x$ è ancora una parabola con ascissa del vertice situata nella media delle due di partenza: 
%$$
%\left\{\begin{array}{l}
%                   {y_1 = k(x-x_1)^2}\\
%                   {y_2 = k(x-x_2)^2}\\
%\end{array}\right.
%\Rightarrow
%y_3 = y_1 + y_2 = (2k)x^2 + (-2k(x_1+x_2))x + (k(x_1^2+x_2^2))
%$$
%$y_1$ ha vertice $(x_1,0)$, $y_2$ ha vertice $(x_2,0)$ mentre il vertice di $y_3$ ha ascissa che vale proprio ($x_1$+$x_2$)/2.\\ 
%Grazie a questa proprietà non solo siamo certi che il massimo di questo funzionale è unico, ma anche che sotto l'azione del solo funzionale di coordinazione la posizione all'istante $t+1$ della telecamera i-esima tenderà (compatibilmente al vincolo di velocità massima a cui è sottoposta) alla posizione intermedia "suggerita" dalle telecamere adiacenti: questo algoritmo è senz'altro convergente (e cioè porta le telecamere a disporsi a distanza $L$ ciascuna dall'altra) perchè la prima e l'ultima hanno posizione che dipende solo da una telecamera adiacente; esse quindi dopo pochi passi si dispongo a distanza $L$ (rispettivamente dalla seconda e dalla penultima) e poi a cascata in pochi passi anche quelle intermedie fanno altrettanto.
%
%\paragraph{Scelta del funzionale di patrolling}
%La scelta quadratica di $Jpos_i(x,t)$ è legata al fatto che volevamo avere due funzionali che fossero confrontabili per somma diretta.
%
%\paragraph{Scelta dell'ottimo all'istante t+1}
%Come detto precedentemente l'ottimo all'istante $t+1$ per la telecamera i-esima è:
%\begin{equation}
%	x_{ott_i}(t+1) = \arg\max_x [Jpos_i(x,t) + Jcoor_i(x,t)]
%	\label{eq:so1}
%\end{equation} 
%
%Il massimo risultante dalla somma dei due è quindi funzione di entrambi i funzionali: a seconda di quale dei due prevale, il sistema tende a coordinarsi oppure a monitore il percorso.
%\\Il nostro grado di libertà su cui agire per fare in modo che nel primo transitorio prevalga il funzionale di coordinazione (per allineare le telecamere) e a regime invece quello di patrolling è il parametro $k$.
%
%\begin{figure}[!ht]
%\centering
%\includegraphics[width=15cm,height=7cm]{SoluzioneCasoBase}
%\caption{Esempio di simulazione del caso base}
%\end{figure}
%
%
%\paragraph{Euristica del parametro \textit{k}:}
%Valori di $k$ troppo piccoli impediscono al sistema di coordinarsi, in quanto il funzionale di patrolling assume troppo presto valori dominanti rispetto a quello di coordinazione (il massimo assoluto cioè è imposto da Jpos); ma valori di $k$ troppo grandi provocano delle oscillazioni a regime intorno agli estremi della sezione da monitorare; intuitivamente perchè dopo ciascuna spazzolata è necessario aspettare un $\Delta T$ prima che il funzionale di patrolling torni a dominare quello di coordinazione.
%\\Abbiamo quindi intuito la necessità che ci fosse un trade off tra le due esigenze, sperando di poter determinare nel primo caso una condizione esplicita del tipo $k > c_1$ (condizione 1), nel secondo invece del tipo $k < c_2$ (condizione 2): se il $c_1$ trovato fosse stato maggiore di $c_2$ questo avrebbe significato che la nostra procedura avrebbe avuto il limite intrinseco di coordinare le telecamere a patto di produrre delle piccole oscillazione agli estremi durante il patrolling a regime. Siamo riusciti a produrre una relazione esplicita solo nel secondo caso: nel primo purtroppo il fatto che il funzionale di patrolling non abbia ancora una forma di ramo di parabola (si forma tale ramo solo dopo una spazzolata completa) rende molto difficile un'analisi analitica; tuttavia da uno studio accurato del nostro algoritmo e dall'osservazione di molte simulazioni sembra proprio che ``$c_1$ sia maggiore di $c_2$'' e non esista quindi un valore limite che soddisfi entrambe le condizioni.
%\subparagraph{Analisi della condizione 2:}
%A regime il problema delle oscillazioni si crea agli estremi. Come detto questo è dovuto al fatto che il massimo del potenziale di coordinazione ``vince'' su quello di patrolling per un $\Delta T$. 
%\\Supponiamo di trovarci nell'estremità destra di pattugliamento in posizione \mbox{$x = 950$}. Il periodo ottimo a regime in assenza di oscillazioni vale: $$T = 2(900/V_{max}) = 2(900/10) = 180$$
%Affinchè ciò si verifichi è necessario che:
%$$J_i(50,t) = (T/2)^2 - 2k(50-950)^2 \geq 0$$
%in questo modo il massimo all'istante $t+1$ sarà proprio dalla parte opposta (in posizione 50) e questa è la condizione che a regime fa spostare il nostro sistema. Risolvendo risulta:
%$$ k \leq 1/200 = 0.005$$ 
%valore che si riscontra precisamente nelle simulazioni.  
%
%
%\begin{figure}[!ht]
%\centering
%\includegraphics[width=15cm,height=7cm]{DettaglioOscillazione}
%\caption{Dettaglio di oscillazione ad un estremo: caso con $k$ troppo elevato}
%\end{figure}
%
%\begin{figure}[!ht]
%\centering
%\includegraphics[width=15cm,height=7cm]{TelecamereNnAllineate}
%\caption{Telecamere non allineate: caso con $k$ troppo piccolo}
%\end{figure}
%
%
%\newpage
%\section{Analisi del caso generale - Approccio più profondo}
%Dopo aver indagato un caso molto semplificato del nostro problema, senza la dinamica dell'evento, abbiamo deciso di fare un passo indietro per capire bene quale potesse essere una procedura da adottare che ci permettesse di risolverlo in un caso più generale. Per prima cosa i nostri sforzi si sono concentrati nel cercare di descrivere il comportamento a regime delle nostre telecamere per garantire copertura ottima in assenza di evento.
%
%\subsection{Analisi di ottimalità}\label{ado}
%\paragraph{Ipotesi generali}
%\begin{enumerate}
%\item $C_i$ di ampiezza arbitraria
%\item $C_i$ che si possono sovrapporre ($C_i \cap C_j \neq \emptyset$ in generale)
%\item $V_{i_{max}}$ arbitrarie 
%\end{enumerate}
%Ci siamo quindi posti in ipotesi del tutto generali.
%\paragraph{Obiettivo}
%$$\min_{A_i}[J(x,t)], \quad \mbox{con J(x,t) =} \left\{\begin{array}{l}
%                   {0 \quad \mbox{se $\exists \,N_i$ che copre $x$ all'istante $t$}}\\
%                   {(t-t_{ultimaVisita})^2 \quad \mbox{altrimenti}}\\
%                   \end{array}\right.$$
%con $x \in$ [0\ldots $L_{tot}$], con $L_{tot}$ la lunghezza totale del percorso da monitorare, $N_i$ telecamera i-esima.\\
%Cioè ci siamo chiesti se esista a regime una scelta delle sezioni di copertura di ciascuna telecamera ($A_i$), che garantisca di minimizzare l'indice $J$. In altri termini:
%\begin{equation}
%	\exists \left\{A_i\right\} | \left\{A_i\right\} = \arg \min_{A_i}[\max J(x,t)] = \arg \min_{A_i} \left\| J(x,t)  \right\|_{\infty}
%	\label{eq:inf}
%\end{equation}
%Si tratta di una scelta molto ragionevole che garantisce di avere un limite superiore $T_{max}$ entro il quale ciascun punto del percorso viene visitato.
%\\Abbiamo quindi cercato di dimostrare quale potesse essere la traiettoria ottima (e quindi l'insieme delle $A_i$) che ci permettesse di avere questa ottimizzazione. A tal proposito abbiamo elaborato due possibili dimostrazioni: entrambe concludono essenzialmente la stessa cosa, tuttavia mettono in luce aspetti diversi di tale problema, pertanto abbiamo ritenuto utile riportarle entrambe.
%
%\subsubsection{Dimostrazione 1}
%Consideriamo $T$ il tempo massimo necessario per visitare a regime tutti i punti del percorso (ciò significa che a partire da un generico istante a regime $T_0$ in $T_0+T$ visito tutti i punti). Senz'altro in $T$ allora vale che la somma degli spazi percorsi dalle telecamere è maggiore (o almeno uguale) all'intero percorso da monitorare:
%\begin{equation}
%	\sum_{i=1}^{N}{s_i} \geq L
%	\label{eq:d11}
%\end{equation}
%con $s_i$ lo spazio effettivamente percorso dalla telecamere (in generale può succedere che $A_i \leq s_i$, dove con $A_i$ si intende la sezione del percorso effettivamente coperta in $T$ dalla telecamera i-esima che al massimo vale $C_i$).\\
%Posto che a regime abbia buon senso considerare che, per il tipo di minimizzazione che si sta effettuando, ciascuna telecamera si muova a velocità pari alla sua $V_{max}$ si ottiene:
%\begin{equation}
%	\sum_{i=1}^{N}{V_{i_{max}}T} \geq L \quad \Rightarrow \quad T \geq \frac{L}{\sum_{i=1}^{N}{V_{i_{max}}}}
%	\label{eq:d12}
%\end{equation}
%ma minimizzare $\left\|J(x,t)\right\|_{\infty}$ è equivalente a minimizzare proprio questo tempo $T$ necessario per visitare tutti i punti $\Rightarrow$ 
%\begin{equation}
%	T_{ott} = \frac{L}{\sum_{i=1}^{N}{V_{i_{max}}}}
%	\label{eq:d13}
%\end{equation}
%che tornando indietro significa far valere l'ugualianza nella relazione iniziale:
%\begin{equation}
%	\sum_{i=1}^{N}{s_i} = L
%	\label{eq:d14}
%\end{equation} 
%Analizziamo attentamente l'ultima uguaglianza. Si sta dicendo che la somma degli spazi percorsi in $T = T_{ott}$ è proprio pari all'intera lunghezza da monitorare; questo può voler dire solo una cosa: all'ottimo ciascuna telecamera monitora una parte del percorso ($A_i$) che le è preposta, con $T_{ott}$ pari al tempo necessario per effettuare una spazzolata completa da un estremo all'altro; vale quindi:
%\begin{equation}
%	T_{oscill} = \mbox{2 } T_{ott} 
%	\label{eq:d15}
%\end{equation}
%%\\Occorre però fare delle precisazioni. L'ottimo a cui siamo giunti è uno dei possibili (infatti ad esempio, seppur %ragionevolmente, abbiamo supposto che le telecamere si muovessero a velocità Vmax) e si realizza quando 
%\\Ricapitoliamo il risultato a cui siamo giunti: esiste un ottimo a regime per il problema di minimizzazione posto, in cui ciascuna telecamere monitora a velocità massima una sezione $A_i$ ad essa preposta, le $A_i$ hanno intersezione nulla e per questo motivo non c'è bisogno di alcuna coordinazione tra le telecamere. 
%\\Possiamo considerare l'insieme delle soluzioni ${A_i}$ non solo un ottimo del nostro problema di minimizzazione, ma anche una soluzione di equilibrio del nostro sistema. Resta quindi da indagare la stabilità di questa configurazione, che sarà strettamente legata all'algoritmo che implementeremo e che ci dovrà permettere, a partire da una configurazione iniziale arbitraria, di portare il sistema allo stato desiderato.
%
%\subsubsection{Dimostrazione 2}
%Il criterio di ottimalità $\arg \min_{A_i}[\max J(x,t)] = \arg \min_{A_i} \left\| J(x,t)  \right\|_{\infty}$ equivale a minimizzare il tempo massimo che trascorre tra una visita e l'altra della telecamera a ciascun punto del percorso, in quanto il funzionale $J(x,t)$ cresce in ogni punto in modo quadratico col tempo, e viene annullato quando la telecamera passa per quel punto.
%
%\paragraph{Ipotesi}
%
%\begin{enumerate}
% \item La telecamera abbia un field of view puntiforme.
% \item La $i$-esima telecamera possa muoversi in un intervallo $C_i$, $C_i \subset \mathcal{L}$ dove $\mathcal{L}$ corrisponde al percorso totale, $|\mathcal{L}|=L$.  %=[c_i^-,c_i^+]$.
% \item $\forall i$, vi sia un intervallo $\mathcal{W}_i \subset C_i$ t.c. $\mathcal{W}_i \cap C_j = \emptyset, \  \forall j \neq i$.
%\end{enumerate}
%
%\paragraph{Premessa}
%
%L'ipotesi 1 viene posta per semplificare la trattazione e la notazione, ma può facilmente essere sostituita nel caso generale con un ipotesi differente, ossia che il field of view abbia misura minore della $\mathcal{W}_i$, il che generalmente è verificato nelle nostre prove (fov pari a $1/10$ delle $C_i$).
%
%L'ipotesi 3 impone che ogni $i$-esima telecamera abbia necessariamente un comportamento oscillatorio, per andare a coprire costantemente almeno la sezione $\mathcal{W}_i$ che solo ad essa compete, e dove altrimenti l'indice andrebbe a divergere. Non è restrittivo assumere che ogni telecamera assuma quindi un andamento periodico con semiperiodo $T_i$, dove il $T_i$ a priori può essere diverso da camera a camera. Definiamo con $A_i$ la sezione che la telecamera copre effettivamente durante questo andamento periodico: in un periodo $2T_i$ ogni punto di $A_i$ viene raggiunto. Deve dunque valere la catena di inclusioni
%\begin{equation}
%	\mathcal{W}_i \subseteq A_i \subseteq C_i, \quad \forall i.
%	\label{eq:d21}
%\end{equation}
%
%Si noti inoltre che l'ipotesi 3 non esclude la possibilità che le sezioni $C_i$ e $C_{i+1}$ si intersechino ($\mathcal{W}_i$ può in effetti essere un intervallo piccolo a piacere sotto queste ipotesi), ma impone che $C_i \cap C_{i+2}= \emptyset$.
%
%\paragraph{Una soluzione ottima}
%
%
%Costruiamo ad-hoc una traiettoria particolare, che poi dimostreremo avere caratteristiche di ottimalità rispetto al suddetto indice. Supponiamo che le telecamere si muovano tutte con lo stesso periodo $2T$, in fase, e andando alla velocità massima $V_{i,max}$ ad esse consentita da un bordo all'altro delle $A_i$. Vogliamo che le sezioni $A_i$ siano adiacenti e non intersecantisi, di modo che
%\begin{equation}
%	L=\sum_{i=1}^N |A_i| = \sum_{i=1}^N T V_{i,max} = T \sum_{i=1}^N V_{i,max}
%	\label{eq:d22}
%\end{equation}
%Con questo moto, l'indice assume il valore massimo in corrispondenza delle ``punte'' della traiettoria a onda triangolare, dove il tempo trascorso dalla passata precedente è massimo e pari a
%\begin{equation}
%	2T=\frac{2L}{\sum_{i=1}^N V_{i,max}}
%	\label{eq:d23}
%\end{equation}
%Si noti che il fatto che le onde partano in fase è irrilevante ai fini di questo valore di massimo. Si noti inoltre che questa è la traiettoria ottima solo quando è \emph{realizzabile}. E' in altre parole necessario verificare a posteriori che le $A_i$ ottenute col procedimento suddetto siano contenute nelle $C_i$, ovvero nella parte di percorso in cui la $i$-esima telecamera può effettivamente muoversi.
%
%\begin{figure}[htb!]
%\centering
% \includegraphics[width=15cm,height=8cm]{fig_pier/CamInFase}
%\caption{Traiettoria ottima (caso particolare: camere in fase e con la stessa $V_{max}$)}
%\label{fig:opt}
%\end{figure}
%
%\paragraph{Dimostrazione dell'ottimalità}
%
%Si dimostra che qualsiasi modifica delle $A_i$ porta in queste condizioni ad un valore massimo dell'indice strettamente peggiore del valore precedente. Infatti, per modificare le $A_i$, si deve necessariamente fare in modo che una di esse abbia misura superiore a quella precedente (se una delle $A_i$ viene ridotta rispetto al caso precedente, ce ne sarà un'altra che dovrà crescere per ottenere alla fine la copertura totale).  Indichiamo con $\{ \bar{A_i} \}$ la nuova partizione. $\exists i \ t.c \ |\bar{A_i}|>|A_i|$. Sia $\delta = |\bar{A_i}|-|A_i|$. Possiamo supporre di aver spostato solo l'estremo superiore, essendo facilmente ripetibile il ragionamento successivo al caso generale. L'importante è che in ogni caso \emph{almeno una} delle due cose seguenti dovrà accadere:
%\begin{itemize}
% \item Si dovrà abbassare l'estremo inferiore di $\bar{A_i}$, e questo propaga una criticità verso l'alto
% \item Ovvero si dovrà alzare quello superiore, portando a una criticità verso il basso.
%\end{itemize}
%
%La criticità cui si accennava poc'anzi verrà ora descritta. Per quanto già detto la camera $i$ deve sempre coprire l'intervallo $\mathcal{W}_i$ in modo periodico. Supponiamo di considerare il tratto di moto in cui la camera passa per $\mathcal{W}_i$, va a toccare l'estremo superiore di $\bar{A_i}$ e ripassa per $\mathcal{W}_i$. Per assicurare la massima copertura in $2T$ all'interno di $\bar{A_i}$, bisogna ancora richiedere che la telecamera vada alla massima velocità $V_{i,max}$. Tuttavia anche in questo modo si riesce ad assicurare la copertura solo in una fascia di altezza $|A_i|$, in quanto la base del triangolo che si ottiene in questo modo misura proprio $2|A_i|V_{i,max}=2T$. Bisogna richiedere quindi che al di sotto della base di tale triangolo cada un punto della traiettoria sottostante. Ciò può essere fatto succedere in due modi:
%\begin{itemize}
% \item Traslando la $A_{i-1}$ verso l'alto di $\delta$, se il periodo della camera $i-1$ è minore di quello della $i$
% \item Allargando la $A_{i-1}$ verso l'alto di $\delta$
%\end{itemize}
%
%Entrambe le soluzioni proposte ripresentano il problema precedente alla base della $A_{i-1}$, dove si ripresenta una carenza di copertura in una fascia di ampiezza $\delta$.
%% da controllare, potrebbe dover essere riscalato per effetto del rapporto tra le velocità ma cio che conta è che c'è una fascia non coperta in 2T di ampiezza non nulla.
%Procedendo in questo modo si propaga questa carenza verso l'estremo, dove però non è possibile compensare in nessun modo: al bordo si avrà una fascia di ampiezza $\delta$ (eventualmente riscalata nel caso di velocità diversa tra le camere) in cui il tempo massimo tra una copertura e l'altra supera il valore ottimo pari a $2T$.
%
%\begin{figure}[htb!]
%\centering
% \includegraphics[width=15cm,height=8cm]{fig_pier/CamDilata}
%\caption{Traiettoria non ottima con traslazione delle camere inferiori}
%\label{fig:nnopt1}
%\end{figure}
%
%\begin{figure}[htb!]
%\centering
% \includegraphics[width=15cm,height=8cm]{fig_pier/CamDilataAll}
%\caption{Traiettoria non ottima con dilatazione delle camere inferiori}
%\label{fig:nnopt2}
%\end{figure}
%
%\newpage
%
%\subsubsection{Analisi della soluzione ottima}\label{aso}
%La soluzione ottima sopra determinata è raggiungibile se e solo se valgono i seguenti vincoli lineari: 
%%che sono calcolabili del tutto off line noti i parametri del sistema:
%\begin{itemize}
%\item $C_{1_{sup}} \geq L_1$
%\item $C_{i_{inf}} \leq L_{i-1}$
%\item $C_{i_{sup}} \geq L_i$
%\item $C_{N_{inf}} \leq L_{N-1}$
%\end{itemize}
%
%con $L_i = \sum_{j=1}^i{A_j}$.
%\begin{figure}[!ht]
%\centering
%\includegraphics[width=0.8\textwidth]{VincoliDiOttimalitaBis}
%\caption{Esempio in cui i vincoli di ottimalità sono soddisfatti}
%\end{figure}\\
%In pratica è necessario che l'ottimo delle sezioni sopra calcolato sia compatibile con le coperture a priori che ciascuna telecamere può effettuare; un risultato importante è che la valutazione della soluzione ottima può essere fatta del tutto offline e questo ci permette già a priori di sapere se è possibile o meno raggiungere l'ottimo (ed eventualmente possiamo modificare qualche parametro per raggiungerlo).\\
%Si può inoltre osservare che condizione necessaria affinchè ciò avvenga è che:
%\begin{equation}
%	A_i \leq C_i
%	\label{eq:ao1}
%\end{equation}
%
%I vincoli da soddisfare sopra mostrati possono sembrare molto forti. In realtà si può intuire che essi possono essere soddisfatti se si verificano queste due condizioni ragionevoli (condizioni sufficienti):
%\begin{enumerate}
%\item La lunghezza di ciascuna $C_i$ è proporzionale alla velocità della telecamera i-esima
%\item $\nexists\, i,j: \, C_i \subseteq C_j \mbox{ e } (C_{i+1}-C_i)$ sia una frazione troppo piccola di $C_{i+1}$
%\end{enumerate}
%La prima delle due condizioni dice che le telecamere più veloci possono avere una copertura a priori maggiore e viceversa (ipotesi ragionevole in quanto non ha molto senso che ad una telecamera molto lenta venga attribuita una copertura molto grande).\\
%La seconda invece è un pò più delicata: non dice che non ci deve essere ridondanza nella copertura del percorso (infatti se per assurdo a ciascuna telecamera fosse permesso di coprire tutto il percorso di certo i vincoli di ottimalità sarebbero soddisfatti pur non realizzandosi questa condizione), bensì che essa dovrebbe essere fatta in modo ``furbo'', ad esempio come nel nostro caso, in modo tale da garantire il tracking di un evento (le coperture a due a due si sovrappongono in parte agli estremi) escludendo invece ad esempio il caso che due telecamere coprano praticamente la stessa zona del perimetro. 
%
%\begin{figure}[!h]
%\centering
%\includegraphics[width=1\textwidth]{CoperturaBuona}
%\caption{Esempio in cui la copertura può soddisfare l'ottimo}
%\end{figure}
%
%\begin{figure}[!ht]
%\centering
%\includegraphics[width=1\textwidth]{CoperturaCattiva}
%\caption{Esempio in cui la copertura probabilmente non soddisfa l'ottimo}
%\end{figure}
%
%\subsubsection{Osservazioni ulteriori sulla traiettoria ottima; sviluppi futuri}
%
%Come evidenziato nelle dimostrazioni proposte, quando la traiettoria ottima è realizzabile, non è più così importante che le telecamere vengano coordinate in modo da essere in fase. Si è fatta quindi una prova rimuovendo il potenziale di coordinazione e introducendo sovrapposizione parziale agli estremi. Le camere adiacenti condividono l'informazione sul potenziale di posizione nella zona sovrapposta, di modo che se la camera $i+1$ entra nella sezione $C_i$, il potenziale che la camera $i$ ha in memoria viene annullato nei punti visitati dalla $i+1$. In questo modo, il sistema tende ad avvicinarsi spontaneamente a una situazione di regime in cui le camere coprono la sezione ottima, e si trovano a due a due in opposizione di fase. Questa traiettoria viene proposta come traiettoria ottima anche nell'articolo di Kingston et al., \emph{Decentralized Perimeter Surveillance Using a Team of UAVs}, dove però la scelta è giustificata dal fatto che in quel caso si cerca di far viaggiare nel modo più veloce possibile dell'informazione da un estremo all'altro del percorso, posto che gli agenti possano comunicare solo quando si trovano a contatto. Nel nostro caso, la scelta di richiedere contatto tra gli agenti potrebbe essere ragionevole, e in particolare eviterebbe la possibilità che un intruso possa muoversi liberamente nella sezione compresa tra due telecamere adiacenti, seguendo il loro moto periodico per rimanere sempre nella fascia non coperta, e non essere in questo modo mai visto. Nel seguito si tratterà dunque di scegliere la strategia migliore (camere in fase/camere in opposizione di fase) in riferimento a
%
%\begin{itemize}
% \item Riapplicabilità dell'algoritmo di controllo al caso sub-ottimo
% \item Robustezza
% \item Raggiungimento di un caso sub-ottimo quando una delle camere abbandona il patrolling per fare il tracking
% \item Estendibilità e raggiungimento di una condizione asintotica quando la sovrapposizione è molta (es. doppia sovrapposizione per tutti i punti del percorso).
%\end{itemize}
%
%\begin{figure}[htb!]
%\centering
% \includegraphics[width=15cm,height=8cm]{fig_pier/sovrapp250}
%\caption{Traiettoria telecamere con sovrapposizione del 25 \% alle adiacenze}
%\small{Le traiettorie tendono ad assomigliare alla traiettoria ottima con camere in opposizione di fase già col solo funzionale di posizione.}
%\end{figure}
%
%\begin{figure}[htb!]
%\centering
% \includegraphics[width=15cm,height=8cm]{fig_pier/sovrapp500}
%\caption{Traiettoria telecamere con sovrapposizione del 50 \% alle adiacenze}
%\small{Il nuovo potenziale di coordinazione dovrà assicurare il raggiungimento di una condizione asintotica anche in questo caso, dove il solo funzionale di posizione mostra di essere non sufficiente.}
%\label{fig:nosinc}
%\end{figure}
%
%\newpage
%
%\section{Imposizione della traiettoria ottima tramite funzionali parabolici}
%
%\subsection{Impostazione generale}
%
%Cerchiamo di riutilizzare la struttura finora impiegata per imporre la traiettoria ottima al sistema, ovvero il partizionamento del percorso in zone di interesse di competenza di una singola telecamera. Pensando di indurre ancora una coordinazione in fase tra le telecamere, è possibile indurre il partizionamento ottimo imponendo in modo adeguato la distanza tra due telecamere adiacenti. La coordinazione in fase è a priori ancora possibile in quanto, anche in presenza di camere con velocità differenti, il moto ottimo per il sistema è quello che vede uno stesso periodo di oscillazione (quello minimo) per tutte le telecamere.
%
%Si può altresì fare la seguente osservazione: per quanto detto al precedente paragrafo, togliendo il potenziale di coordinazione e lasciando che il sistema evolva per effetto del solo potenziale di posizione in presenza di sovrapposizione tra le sezioni, si arriva in una situazione prossima a quella desiderata, con le camere in opposizione di fase. Ciò è vero se la sovrapposizione non è eccessiva. Uno schema totalmente ridondante non si assesta da sé alla situazione di regime, come mostrato nella figura \ref{fig:nosinc}.
%
%Si può dunque congetturare che se si riesce in qualche modo a indurre la traiettoria in opposizione di fase con le parabole di coordinazione, sarà possibile utilizzare un valore inferiore del coefficiente $k$ con cui vengono sommate al potenziale di posizione, e ottenere comunque la coordinazione, in quanto la traiettoria in opposizione di fase è più prossima al comportamento ``naturale'' del sistema. Le notazioni usate sono schematizzate nella figura \ref{fig:notapar}, e sono istituite in vista di una implementazione locale dell'algoritmo. I valori $c_i^-$ e $c_i^+$ sono dati e quantificano la sovrapposizione agli estremi con la telecamera adiacente; i valori $a_i^-$ e $a_i^+$ limitano invece la traiettoria di patrolling e andranno ora calcolati.
%
%\begin{figure}
% \centering
% \includegraphics[width=16cm]{fig_pier/sezioni}
% \caption{Notazione usata nel calcolo dei potenziali di coordinazione}
% \small{$c_i^-$ e $c_i^+$: lunghezza sovrapposta all'estremo inferiore e superiore\\}
% \small{$a_i^-$ e $a_i^+$: zone da non visitare all'estremo inferiore e superiore secondo la traiettoria ottima}
%\label{fig:notapar}
%\end{figure}
%
%Il calcolo di $T_{ott}$ si può ottenere come segue (si terrà d'ora in poi conto del fatto che il \emph{field of view} della $i$-esima telecamera $fov_i$ ha misura non nulla):
%\begin{equation}
%	T_{ott} = \frac{L}{\sum_{i=1}^N v_{i,max}} = \frac{\sum_{i=1}^N L_i - c_i^+ -fov_i}{\sum_{i=1}^N v_{i,max}}
%	\label{eq:ig1}
%\end{equation}
%dove si è evidenziato come il $T_{ott}$ possa essere ottenuto come somma di proprietà locali delle telecamere, e quindi una possibilità aperta è quella di ottenere il suo calcolo con algoritmi al consenso. \textcolor{red}{E' da puntualizzare che le $A_i$ ottime sono le zone in cui si deve muovere il centro camera. Nel fatto, quindi, la scena vista effettivamente dalla camera entra per $fov/2$ nelle $a_i$.}
%
%Dal $T_{ott}$ si ricava come già visto la lunghezza delle sezioni $A_i$, e questo può essere fatto a livello locale:
%\begin{equation}
%	A_i=T_{ott} v_{i,max}
%	\label{eq:ig2}
%\end{equation}
%
%Infine, si devono tradurre questi valori nei bordi effettivi delle sezioni da monitorare, ovvero si deve ricavare il valore di $a_i^-$ e $a_i^+$. Si propone qui un semplice algoritmo ricorsivo che ottiene il calcolo di tali valori a partire dalla prima camera, con comunicazione passo passo fino all'N-esima. Purtroppo per svolgere questo calcolo sembra sia necessario svolgere necessariamente una procedura di comunicazione passo-passo, e non pare sia possibile applicare procedure asintotiche del tipo al consenso.
%
%\begin{eqnarray*}
%&& \quad a_1^- = \frac{fov_1}{2} \\
%&& \quad a_1^+ = L_1 - a_1^- - A_1\\ \\
%&& \mbox{for } i=2:N \\
%&& \quad a_i^- = c_{i-1}^+ - a_{i-1}^+ + \frac{fov_{i-1}}{2} + \frac{fov_{i}}{2} \\
%&& \quad a_i^+ = L_i - a_i^- - A_i\\
%&& \mbox{end}
%\end{eqnarray*}
%
%Ricaviamo ora la posizione in cui centrare i funzionali di coordinazione per indurre la traiettoria ottima. Sia $x_i(t)$ la posizione assunta dalla $i$-esima telecamera, supponendo $x_i(t)=0$ quando la telecamera si trova nella posizione estrema inferiore che fisicamente può raggiungere, e viceversa $x_i(t)=L_i$ all'altro estremo. La distanza da indurre tra le telecamere deve essere opportunamente calcolata per tenere conto delle possibili differenze di velocità tra le camere e dalla a priori differente misura delle lunghezze degli estremi sovrapposti. Consideriamo la quantità normalizzata rispetto alla lunghezza ottima (\textcolor{red}{Attenzione, forse qui e pure nel codice manca qualche correzione legata al fov})
%\begin{equation}
%	\xi_i(t)=\frac{x_{i-1}(t)-a_i^-}{A_i}
%	\label{eq:ig3}
%\end{equation}
%Tale quantità varierà tra 0 e 1 quando la telecamera percorre la sezione ottima ad essa assegnata. Se le telecamere adiacenti si scambiano l'informazione normalizzata legata allo $\xi_i(t)$, saranno in grado di calcolare il punto dove centrare il funzionale di coordinazione semplicemente denormalizzando rispetto alla misura della loro sezione ottima. E' poi possibile indurre opposizione di fase tra le camere adiacenti centrando la parabola di coordinazione nel punto $1 - \xi_i(t)$ anziché in $\xi_i(t)$.
%
%Più in dettaglio, l'espressione del funzionale di coordinazione ``visto'' dalla camera $i$-esima e relativo alle due adiacenti
%\begin{equation}
%	Jcoor_i(x,t) = -k_i(x-pos_{i-1}(t))^2  - k_i(x-pos_{i+1}(t))^2
%	\label{eq:ig4}
%\end{equation}
%induce la traiettoria ottima in fase con il seguente valore dei vertici
%\begin{eqnarray*}
%pos_{i-1}(t)=A_i\xi_{i-1}+a_i^- \\
%pos_{i+1}(t)=A_i\xi_{i+1}+a_i^-
%\end{eqnarray*}
%mentre induce la traiettoria ottima in opposizione di fase con i vertici
%\begin{eqnarray*}
%pos_{i-1}(t)=A_i(1-\xi_{i-1})+a_i^- \\
%pos_{i+1}(t)=A_i(1-\xi_{i+1})+a_i^-
%\end{eqnarray*}
%
%Si noti che il parametro $k_i$ che quantifica l'altezza del funzionale di coordinazione è stato indicizzato in $i$ in quanto andrà evidentemente riscalato camera per camera, in modo conforme alle $v_{i,max}$. Infatti, il funzionale di posizione è funzione monotona del tempo, mentre quello di coordinazione è funzione della distanza dalla posizione indotta. Supponiamo che la camera $i$ si sia mossa alla velocità massima possibile dall'estremo inferiore a quello superiore della sezione ottima, e cerchiamo il $\bar{k_i}$ che fa assumere esattamente lo stesso valore in modulo ai funzionali di posizione e coordinazione all'estremo inferiore nell'istante in cui si arriva all'estremo superiore. In questo modo, un istante dopo il funzionale di posizione supererà quello di coordinazione all'estremo superiore, richiamando indietro la telecamera. Ciò accade quando
%\begin{equation}
%	{T_{ott}^2}=2\bar{k_i}A_i^2 \quad \Rightarrow \bar{k_i}=\frac{T_{ott}^2}{2 A_i^2}
%	\label{eq:ig5}
%\end{equation}
%Il fattore 2 tiene conto del fatto che in realtà si sommano due parabole di coordinazione per ogni camera (escluse quelle agli estremi). Decidiamo quindi di impiegare i valori
%\begin{equation}
%	k_i=\bar{k_i} K
%	\label{eq:ig6}
%\end{equation}
%dove $K$ è un parametro globale sul quale agiamo per valutare il comportamento del sistema imponendo una maggiore o minore coordinazione.
%
%\subsection{Prova sperimentale}
%
%Si è a questo punto provato a implementare nel codice preesistente le soluzioni sopra proposte. Si è cercato di mantenere un certo livello di flessibilità nel codice, ovvero si è lasciata la facoltà di indicare la strategia di coordinazione da impiegare: con camere in fase, in opposizione di fase o senza potenziali di coordinazione. Questo ultimo caso era già stato analizzato brevemente in conclusione del paragrafo precedente, e non necessita di ulteriori approfondimenti: senza indurre la coordinazione, le camere fanno il patrolling dividendosi le sezioni in modo approssimato, e non si ha una buona ripartizione delle sezioni quando c'è tanta sovrapposizione.
%
%\paragraph{Camere in fase}
%
%\begin{figure}[htb!]
% \centering
%\includegraphics[width=15cm]{fig_pier/01_fase_400_k=3}
%\caption{Camere in fase, sovrapposizione 40\% agli estremi, K=3}
%\small{Linee orizzontali continue: limiti fisici delle telecamere\\
%Linee orizzontali tratteggiate: limite ottimo delle telecamere}
%\label{fig:fase}
%\end{figure}
%
%
%Imponendo la coordinazione con camere in fase, si ottiene che le telecamere tendono a disporsi alla distanza ottima prefissata. Tuttavia, non si ha la ripartizione in aree di interesse: le traiettorie si compenetrano tra camere adiacenti e si perde la copertura in $2T_{ott}$ agli estremi (figura \ref{fig:fase}). Questo fortunatamente non accade nel caso delle camere in opposizione di fase: la traiettoria delle telecamere adiacenti arriva a un punto di incontro, le telecamere cancellano il massimo verso il quale stanno puntando e in quel momento invertono direzione. Si punterà dunque sull'approccio in opposizione di fase per le prossime prove.
%
%\paragraph{Camere in opposizione di fase}
%
%Imponendo la coordinazione in opposizione di fase, quando la traiettoria ottima è realizzabile, ovvero quando è compresa nelle effettive aree di copertura delle telecamere, essa effettivamente viene raggiunta: le camere si distribuiscono correttamente anche nei casi critici. Proponiamo in particolare il caso con sovrapposizione totale (figura \ref{fig:500ok}) che dava problemi in precedenza (\ref{fig:nosinc}), e il caso con camere con velocità massime diverse (\ref{fig:vidiv}).
%
%\begin{figure}[htb!]
% \centering
%\includegraphics[width=15cm]{fig_pier/02_500_k=3}
%\caption{Camere in opposizione di fase, sovrapposizione 50\% agli estremi, K=3}
%\label{fig:500ok}
%\end{figure}
%
%\begin{figure}[htb!]
% \centering
%\includegraphics[width=15cm]{fig_pier/03_vidiv_k=3}
%\caption{Camere in opposizione fase, sovrapposizione 30\% agli estremi, velocità diverse, K=3}
%\label{fig:vidiv}
%\end{figure}
%
%Si deve però rivedere una considerazione fatta in precedenza: con un K piccolo non si ha la certezza di andare a regime in fase nei casi più critici, ovvero quando c'è tanta sovrapposizione. Nel fatto solo un K maggiore di 1 assicura di arrivare a una situazione di regime (\ref{fig:k05}). Questo impone che il sistema debba necessariamente essere strettamente vincolato per arrivare alla soluzione ottima con questo approccio. E se la soluzione ottima non dovesse essere realizzabile, questo comporta che il sistema non si assesta in modo spontaneo a una eventuale soluzione subottima, ma si porta invece a una condizione non accettabile in cui si producono molte oscillazioni alla ricerca del massimo dei funzionali. Il massimo condiviso si raggiunge solo se le telecamere coinvolte possono effettivamente muoversi nelle zone ottime previste. Si veda la figura \ref{fig:probl} per un esempio di problematica che accade quando la traiettoria ottima non è realizzabile
%
%\begin{figure}[htb!]
% \centering
%\includegraphics[width=15cm]{fig_pier/04_k=05}
%\caption{Camere in opposizione fase, sovrapposizione 50\% agli estremi, velocità diverse, K=0.5}
%\label{fig:k05}
%\end{figure}
%
%\begin{figure}[htb!]
% \centering
%\includegraphics[width=15cm]{fig_pier/05_probl}
%\caption{Camere in opposizione fase, sovrapposizione 10\% agli estremi, velocità diverse, K=3, traiettoria non realizzabile}
%\label{fig:probl}
%\end{figure}
%
%
%\paragraph{Sviluppi futuri} A questo punto, appare chiaro che il prossimo punto importante perché l'algoritmo funzioni bene è ottenere una ripartizione subottima ma realizzabile per le aree di interesse delle telecamere, in quanto vincolare con i funzionali di coordinazione al raggiungimento di una condizione non realizzabile provoca inevitabilmente oscillazioni e non convergenza dell'algoritmo a una traiettoria periodica ``pulita''. Nel paragrafo seguente si descriverà dunque un algoritmo che produca tale ripartizione subottima, e che consenta il calcolo della stessa a livello distribuito. Una volta che le sezioni subottime sono ben definite, è inoltre possibile vincolare in modo più forte le telecamere a non uscire dalla sezione subottima loro assegnata, bloccando a zero il potenziale di patrolling nelle zone da non visitare. In questo modo, non è così cruciale il continuo scambio di informazioni sulla posizione tra camere adiacenti: le camere oscillano scansionando la sezione loro assegnata, e eventualmente si può impiegare il potenziale di coordinazione realizzato per mettere in fase tra loro camere adiacenti che siano caratterizzate dallo stesso $T_{subott}$.
%
%\section{Caso sub-ottimo e robustezza}
%In questa sezione si approfondisce l'analisi della soluzione ottima precedentemente determinata, cercando di stabilire quali possono essere le soluzioni da adottare in casi sub-ottimi (in cui cioè la copertura ottima non sia compatibile con le condizioni iniziali di copertura, paragrafo \ref{aso}) e nei casi in cui vi sia una rottura di una telecamera (analisi di robustezza).
%
%\subsection{Analisi del caso sub-ottimo}
%Come analizzato precedentemente, è possibile che la soluzione ottima non sia compatibile con i vincoli delle telecamere: in tal caso si pone il problema di stabilire quale sia la copertura a regime compatibile con i vincoli, sub-ottima rispetto al problema di minimizzazione dell'indice $J$.
%\\Supponiamo di partire dalla telecamera numero $1$ per l'analisi della compatibilità dell'ottimo con i vincoli del sistema; si può verificare solo un caso sfavorevole (figura \ref{fig:s1}):
%\begin{itemize}
%\item $C_{1_{sup}} < L_1$
%\end{itemize}
%Il che significa che la telecamera $1$, secondo l'ottimo calcolato, dovrebbe sforare il limite di copertura di cui dispone: è necessario quindi che essa percorra il maggior spazio possibile compatibile con il proprio vincolo $C_{1_{sup}}$, al fine di garantire l'ottimo di copertura del residuo del percorso. Sarà quindi poi possibile reimpostare il calcolo della copertura ottima escludendo la telecamera $1$ dal calcolo e considerando solo le restanti $N-1$. Cerchiamo di formalizzare quanto detto con la seguente proposizione.
%\begin{figure}[!htb]
%\centering
% \includegraphics[width=0.6\textwidth]{subottimo1}
%\caption{Vincolo violato nella telecamera 1}
%\label{fig:s1}
%\end{figure}
%
%\paragraph{Proposizione 1:} La copertura ottima del percorso nel caso in cui la telecamera $1$ non possa coprire quanto calcolato con la tecnica vista in sezione \ref{aso}, si ottiene attribuendo alla telecamera 1 la massima lunghezza da coprire compatibilmente ai suoi vincoli, e riapplicando il teorema in sezione \ref{aso} alle $N-1$ telecamere rimaste sulla lunghezza $L-C_1$. In formule:
%\begin{enumerate}
%\item $A_1 = C_1$
%\item $A_i = V_{i_{max}}T_{subOtt} \quad i \neq 1$
%\end{enumerate}
%con 
%\begin{equation}
%	T_{subOtt} = \frac{L - C_1}{\sum_{i=2}^{N}{V_{i_{max}}}}
%	\label{eq:p11}
%\end{equation}
%
%\paragraph{Dimostrazione.} Supponiamo per assurdo che si faccia una scelta diversa di $A_1$ (quindi $A_1 < C_1$). Allora necessariamente le restanti $N-1$ telecamere dovranno coprire una lunghezza $\bar{L} = L - A_1 > L - C_1$, ma quindi:
%\begin{equation}
%	\bar{T} = \frac{L - A_1}{\sum_{i=2}^{N}{V_{i_{max}}}} > T_{subOtt}
%	\label{eq:d1}
%\end{equation}
%
%con $T_{subOtt}$ calcolato come sopra.
%\\Ma il criterio di ottimalità da noi scelto (\ref{eq:inf}) stabilisce di minimizzare il $T_{max}$ di visita di ciascun punto (globalmente), pertanto con la disuguaglinza (\ref{eq:d1}) si è dimostrato che $\forall$ scelta di $A_1 \neq C_1$ si fa peggio, in termini di tempo massimo di non-visita di ciascun punto.
%\\
%La generalizzazione di quanto dimostrato al caso in cui sia una telecamera nel mezzo (con $i \neq 1,N$) o l'ultima, a non soddisfare i vincoli di copertura all'ottimo è immediata.
%\paragraph{Telecamera i-esima nel mezzo:} In tal caso si possono avere diversi casi sfavorevoli:
%\begin{enumerate} 
%\item $C_{i_{inf}} > L_{i-1} \quad \wedge \quad C_{i_{sup}} < L_i$
%\item $C_{i_{inf}} > L_{i-1}$
%\item $C_{i_{sup}} < L_i$
%\item $C_{i_{sup}} < L_{i-1} \quad \vee \quad C_{i_{inf}} > L_{i}$
%\end{enumerate}
%
%\paragraph{1° caso:} è forse quello più semplice da trattare (figura \ref{fig:s4}); la scelta sub-ottima risulta:
%\begin{enumerate}
%\item $A_i = C_i$
%\item $A_j = V_{j_{max}}T_{subottS}, \quad j < i$
%\item $A_j = V_{j_{max}}T_{subottD}, \quad j > i$
%\end{enumerate}
%con 
%\begin{equation}
%	T_{subottS} = \frac{L_{S}}{\sum_{j=1}^{i-1}{V_{j_{max}}}} \qquad T_{subottD} = \frac{L_{D}}{\sum_{j=i+1}^{N}{V_{j_{max}}}}
%	\label{eq:Ic1}
%\end{equation}
%
%La dimostrazione che questa è la scelta giusta, discende immediatamente da quella per il caso $n = 1$: una qualsiasi altra scelta di $A_i < C_i$ porterebbe o per le telecamere alla sua destra o per quelle alla sua sinistra, a coprire un tratto di percorso maggiore ($\bar{L}_{S} > L_{S} \vee \bar{L}_{D} > L_{D}$) con conseguente perdità di ottimalità sulla metà in questione e quindi perdità di ottimalità globale.
%
%\begin{figure}[!htb]
%\centering
% \includegraphics[width=0.6\textwidth]{subottimoi1corretto}
%\caption{Caso sub-ottimo in caso di vincolo violato (tipo 1) in una telecamera nel mezzo}
%\label{fig:s4}
%\end{figure}
%
%\paragraph{2° caso:} in questa situazione (figura \ref{fig:s5})non vi è più simmetria come nel caso precedente. Per le telecamere a sinistra di $i$ la scelta sub-ottima risulta:
%\begin{itemize}
%\item $A_j = V_{j_{max}}T_{subottS}, \quad j < i$
%\end{itemize}
%con 
%\begin{equation}
%	T_{subottS} = \frac{L_{S}}{\sum_{j=1}^{i-1}{V_{j_{max}}}}
%	\label{eq:Ic2}
%\end{equation}
%Mentre per quelle a destra (i-compresa) risulta:
%\begin{itemize}
%\item $A_j = V_{j_{max}}T_{subottD}, \quad j \geq i$
%\end{itemize}
%con 
%\begin{equation}
%	T_{subottD} = \frac{L_{D}}{\sum_{j=i}^{N}{V_{j_{max}}}} = \frac{L-L_{S}}{\sum_{j=i}^{N}{V_{j_{max}}}}
%	\label{eq:Ic3}
%\end{equation}
%In questo modo la sub-ottimalità è garantita: se il margine sinistro fosse stato scelto maggiore del limite di copertura inferiore ($L_{i-1} > C_{i_{inf}}$) allora le telecamere a sinistra della i-esima avrebbe coperto una lunghezza maggiore di quella invece da coprire con questa scelta ($\Rightarrow$ peggioro il $T_{max}$); anche per $i$ e le telecamere alla sua destra si deve riapplicare il criterio (1) per la scelta delle $A_i$: in questo modo si è certi dell'ottimalità anche per le telecamere $j \geq i$ (rispetto alla copertura della parte restante di percorso) e si può verificare anche il caso intuitivamente probabile, che il nuovo margine destro di $i$ sia maggiore di quello precedente ($L_{i_{subott}} > L_{i_{ott}}$).
%
%\begin{figure}[!htb]
%\centering
% \includegraphics[width=0.6\textwidth]{subottimoi2}
%\caption{Vincolo violato (tipo 2) in una telecamera nel mezzo}
%\label{fig:s5}
%\end{figure}
%
%\paragraph{3° caso:} è analogo (figura \ref{fig:s6}) a quello precedente soltanto simmetrizzato; per le telecamere a destra si ha:
%\begin{itemize}
%\item $A_j = V_{j_{max}}T_{subottD}, \quad j > i$
%\end{itemize}
%con 
%\begin{equation}
%	T_{subottD} = \frac{L_{D}}{\sum_{j=i+1}^{N}{V_{j_{max}}}}
%	\label{eq:Ic4}
%\end{equation}
%Mentre per quelle a sinistra (i-compresa) risulta:
%\begin{itemize}
%\item $A_j = V_{j_{max}}T_{subottS}, \quad j \leq i$
%\end{itemize}
%con 
%\begin{equation}
%	T_{subottS} = \frac{L_{S}}{\sum_{j=1}^{i}{V_{j_{max}}}} = \frac{L-L_{D}}{\sum_{j=1}^{i}{V_{j_{max}}}}
%	\label{eq:Ic5}
%\end{equation}
%la dimostrazione della sub-ottimalità è la stessa del caso precedente.
%
%\begin{figure}[!htb]
%\centering
% \includegraphics[width=0.6\textwidth]{subottimoi3corretto}
%\caption{Caso sub-ottimo in caso di vincolo violato (tipo 3) in una telecamera nel mezzo}
%\label{fig:s6}
%\end{figure}
%
%\paragraph{4° caso:} questo è davvero molto improbabile che in un contesto verosimile si verifichi (corrisponde al caso a buon senso scartato, in cui $\exists i,j / C_i \subset C_j$); tuttavia offre degli spunti interessanti per capire a fondo il criterio di ottimalità scelto, pertanto merita anch'esso una breve analisi. Questo caso si verifica quando all'ottimo la sezione di copertura della telecamera i-esima ($A_i$) è al di fuori dello spazio di copertura ammissibile; ciò significa che il segmento $A_i$ dovrà essere in parte coperto da $i-1$ e in parte da $i+1$. Tale soluzione si può realizzare con un criterio di ottimalità ripetendo la procedura di scelta delle $A_i$ con il metodo proposto (1) escludendo dal conto la telecamera $i$:
%\begin{itemize}
%\item $A_j = V_{j_{max}}T_{subott}, \quad j \neq i$
%\end{itemize}
%con 
%\begin{equation}
%	T_{subott} = \frac{L_{tot}}{\sum_{j=1,j \neq i}^{N}{V_{j_{max}}}}
%	\label{eq:Ic6}
%\end{equation}
%\\Applicando le sezioni proposte, in sostanza si sta affermando che nel caso sub-ottimo alla telecamera $i$ non è preposta alcuna copertura ($A_i = 0$, che è sensato possa accedere in quanto come detto all'inizio questo è il caso in cui la telecamera i-esima è del tutto ridondante): ciò non significa che essa però debba essere necessariamente inutile, ma che ai fine di garantire il sub-ottimo globale in termini di $T_{max}$ la sua azione è ininfluente: tuttavia una sua azione locale di copertura entro i suoi limiti ammissibili, è comunque utile per diminuire localmente entro la sua copertura il tempo di non visita in quella zona, creando così un ottimo locale migliore di quello globale.
%
%\paragraph{Telecamera N-esima finale:} In tal caso ci si trova nella situazione simmetrica rispetto alla prima telecamera. L'unico caso sfavorevole si manifesta quando (figura \ref{fig:s2}):
%\begin{equation}
%	C_{N_{inf}} > L_{N-1}
%	\label{eq:tnf1}
%\end{equation}
%e cioè all'ultima telecamere è richiesto di coprire una sezione del percorso che precede il suo limite inferiore di copertura.
%\begin{figure}[!htb]
%\centering
% \includegraphics[width=0.6\textwidth]{subottimoN}
%\caption{Vincolo violato nella telecamera N}
%\label{fig:s2}
%\end{figure}
%
%\begin{figure}[!htb]
%\centering
% \includegraphics[width=0.6\textwidth]{subottimoNcorretto}
%\caption{Caso sub-ottimo in caso di vincolo violato nella telecamera N}
%\label{fig:s3}
%\end{figure}
%La scelta sub-ottima di copertura (dimostrazione del tutto analoga al caso n=1, figura \ref{fig:s3}) si ottiene imponendo alla telecamera N-esima di coprire il maggior spazio possibile e ricalcolando le sezioni $A_{i}$ per le altre telecamere nel percorso ridotto:
%\begin{enumerate}
%\item $A_N = C_N$
%\item $A_i = V_{i_{max}}T_{subott}, \quad i < N$
%\end{enumerate}
%con 
%\begin{equation}
%	T_{subott} = \frac{L - C_N}{\sum_{i=1}^{N-1}{V_{i_{max}}}}
%	\label{eq:tnf2}
%\end{equation}
%
%\section{Approccio distribuito: consenso o comunicazione passo passo}
%
%Si richiede di risolvere il problema della coordinazione delle telecamere in maniera distribuita. Ciò significa che non è presente una CPU centrale che elabora i dati provenienti da tutti gli agenti, prende decisioni e le trasmette lungo un canale di comunicazione, ma che ogni telecamera è ``intelligente'', ovvero dotata di microprocessore in grado di prendere decisioni autonome, e le informazioni vengono scambiate solo tra le telecamere adiacenti. In generale dunque ogni telecamera conosce le proprie caratteristiche fisiche e, se non ci fosse alcun vincolo di controllo, agirebbe in maniera indipendentente dalle altre, di cui potrebbe ignorare l'esistenza. La necessità di un algoritmo di controllo implica che ogni camera sappia qualcosa riguardo le sue vicine, in modo da poter ``sfruttare'' la sua intelligenza artificiale per coordinarsi con esse. In un caso del tutto generale le telecamere potranno essere di marca e modello diversi e dunque avere caratteristiche fisiche e tecniche diverse le une dalle altre.
%
%\subsection{Analisi dell'ottimo in termini distribuiti}
%Assumendo che ogni telecamera conosca la lunghezza totale $L_{tot}$ del percorso da monitorare e che i field of view ($fov$) varino da camera a camera, la formula che fornisce il tempo ottimo di patrolling è (\ref{eq:ig1}), qui riportata in maniera più semplice:
%\begin{equation}
%	T=\frac{L_{tot} - \sum_i{fov_{i}}}{\sum_{i=1}^N v_{i,max}}
%	\label{eq:aotd1}
%\end{equation}
%Nel seguito consideriamo per semplicità $fov$ puntiformi, quanto verrà detto può essere tranquillamente esteso al caso generale di $fov$ diversi complicando leggermente le equazioni, ma il succo del discorso seguente resta comunque valido e con questa semplificazione è più facilmente afferrabile. La formula (\ref{eq:aotd1}) si riduce dunque a:
%\begin{equation}
%	T=\frac{L_{tot} }{\sum_{i=1}^N v_{i,max}}
%	\label{eq:aotd2}
%\end{equation}
%In tale formula si vede chiaramente che l'unico parametro variante da camera a camera che influenza il calcolo del tempo ottimo è la velocità massima delle singole camere. Questa sarà dunque l'informazione che le camere devono trasmettersi a due a due, sfruttando un approccio distribuito: una comunicazione passo-passo o una tecnica di consenso.
%
%\subsubsection{Comunicazione passo-passo}
%La comunicazione passo-passo consiste nel scambiarsi l'informazione a due a due, per convenienza partendo dalle camere poste ai due estremi del percorso. In tal modo, supponendo che le camere siano in numero pari a $N$, dopo esattamente $N$ passi ogni camera disporrà dell'informazione su tutte le altre e dunque è in grado di calcolare il tempo ottimo secondo la formula (\ref{eq:aotd2}). Ulteriore problema sarà quello di calcolare le sezioni ottime di ogni telecamera, ma si rimanda tale questione in seguito (IMPOSTARE IL RIF AL PARAGRAFO) dal momento che qui interessa il confronto tra le due possibili strategie iniziali.
%
%\subsubsection{Consenso}
%Il fatto che il tempo ottimo dipenda dalla sommatoria delle velocità, suggerisce di ricorrere all'average consensus. 
%La teoria di tale algoritmo afferma che, dato un vettore di condizioni iniziali (che nel nostro caso sono le velocità massime delle telecamere), si può trovare un controllo in grado di far convergere tale vettore alla media sua media. Si può costruire una matrice doppiamente stocastica $P$ per il sistema
%\begin{equation}
%	x_{k+1} = Px_{k}
%	\label{eq:c1}
%\end{equation}
%Lo stato di tale sistema tende asintoticamente al vettore delle medie. È dunque necessario costruire tale matrice $P$, tenendo presente che essa deve descrivere il sistema di comunicazione tra le telecamere: dunque essa sarà del tipo
%$$
%P = \left[ \begin{array}{cccccc}
%	* & * & 0 & \ldots & & \\
%	* & * & *& 0 & \ldots & \\
%	0 & * & * & * & 0 & \ldots \\
%	\vdots & & & & & \ddots \\
%\end{array} \right]
%$$
%Per garantire la doppia stocasticità si può imporre una $P$ del tipo
%$$
%P = \left[ \begin{array}{cccccc}
%	1-\frac{q}{2} & \frac{q}{2} & 0 & \ldots & & \\
%	\frac{q}{2} & 1-q & \frac{q}{2}& 0 & \ldots & \\
%	0 & \frac{q}{2} & 1- q & \frac{q}{2} & 0 & \ldots \\
%	\vdots & & & & & \ddots \\
%	\end{array} \right]
%$$
%con $q$ parametro da scegliere per minimizzare il transitorio. Tuttavia il metodo del consenso, come detto, è asintotico, dunque non è detto che il tempo ottimo che si sceglie dopo un certo numero di passi (sicuramente pari o maggiore a N, tempo di soluzione della comunicazione passo-passo) sia effettivamente quello corretto stabilito dal teorema dimostrato nella sezione \ref{ado}. Per tale motivo e data la complessità maggiore nel risolvere un algoritmo di consenso, la strategia che verrà adottata sarà quella della comunicazione passo-passo.
%
%
%
%
%
%
%
%
% 
